1. Technical Field
This disclosure is generally related to circuits for linear programming and in particular to pulse domain linear programming circuits.
2. Description of Related Art
Typically, a circuit performing time encoding does not process or solve a linear programming problem. Linear programming is a well known mathematical technique for finding an optimized answer to many practical problems in operations research and in many technological arts as well, such as recovery of signals captured by compressed sensing.
Prior art circuits solve linear programming problems using conventional analog signals. Consequently, such prior art circuit utilize analog amplifiers. The accuracy of such prior art circuits is limited by the linearity of the analog amplifier, commonly used in an internal input.
FIG. 1 shows a prior art analog-input time encoder. See also reference 1 identified above. This circuit has a single analog input u(t) and a single pulse output z(t). This circuit encodes analog input signals u(t) into pulse signals z(t). If the analog signal is bandlimited, the encoding can be practically without loss of information. That is, the input u(t) can be recovered from the timing of the output signal z(t). A time decoding machine can be used to recover the analog input u(t) from the asynchronous pulse output z(t). Assuming ideal elements, practically no quantization error is introduced by this encoder. The circuit of FIG. 1 has an input analog linear amplifier (g1), an integrator, a hysteresis quantizer, a feedback element (g3), and an adder (+). This circuit is not used for linear programming or other optimization problems.
FIG. 2 shows a prior art circuit to solve a linear programming problem in an analog domain. See prior art reference 2 identified above. This circuit has n analog inputs and N analog outputs. The circuit of FIG. 2 can solve problems of the type
                              min          ⁡                      (                          f              ⁡                              (                Z                )                                      )                          ⁢                                  ⁢                  s          .          t          .                      {                                                                                                      A                      ×                      Z                                        =                    Y                                                                                                                                                                                            Z                          i                                                ≥                                                  0                          ⁢                                                                                                          ⁢                          i                                                                    =                      1                                        ,                                                                                  ⁢                    …                    ⁢                                                                                  ,                    N                                                                                                          (                  Equation          ⁢                                          ⁢          1                )            
where A is a constraint matrix with n rows and N columns, Y is an input column vector of n analog numbers, Z is an output column vector of N analog numbers, and f is a linear function of the output vector. All of the signals in the circuit of FIG. 2 are conventional analog signals. The circuit of FIG. 2 is shown in a vector symbolic form. The matrix multiplication symbols represent arrays of variable-gain analog amplifiers, such as analog multipliers, and adders. The accuracy of this circuit is limited by the linearity of these variable-gain analog amplifiers.